/**
 * //节点间通路。给定有向图，设计一个算法，找出两个节点之间是否存在一条路径。
 * //
 * // 示例1:
 * //
 * //  输入：n = 3, graph = [[0, 1], [0, 2], [1, 2], [1, 2]], start = 0, target = 2
 * // 输出：true
 * //
 * //
 * // 示例2:
 * //
 * //  输入：n = 5, graph = [[0, 1], [0, 2], [0, 4], [0, 4], [0, 1], [1, 3], [1, 4], [
 * //1, 3], [2, 3], [3, 4]], start = 0, target = 4
 * // 输出 true
 * //
 * //
 * // 提示：
 * //
 * //
 * // 节点数量n在[0, 1e5]范围内。
 * // 节点编号大于等于 0 小于 n。
 * // 图中可能存在自环和平行边。
 * //
 * // Related Topics 深度优先搜索 广度优先搜索 图 👍 62 👎 0
 */

package com.xixi.basicAlgroithms.BreadthWidthFirstSearch;

import java.util.HashMap;
import java.util.Map;

public class ID_interview_04_01_RouteBetweenNodesLcci {
    public static void main(String[] args) {
        Solution solution = new ID_interview_04_01_RouteBetweenNodesLcci().new Solution();
        System.out.println(solution.findWhetherExistsPath(3, new int[][]{{0, 1}, {0, 2}, {1, 2}, {1, 2}}, 0, 2));
    }


    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        boolean[] visited = null;
        boolean foundPath = false;

        Map<Integer, Integer> startMap = null;

        public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) {
            //防止成环，记录下该边是否浏览过
            if (start == target) return true;
            visited = new boolean[graph.length];
            //记录起始点
            startMap = new HashMap<>(n);
            for (int i = 0; i < graph.length; ++i) {
                if (startMap.containsKey(graph[i][0])) {
                    continue;
                } else {
                    startMap.put(graph[i][0], i);
                }
            }

            dfs(n, graph, start, target, start);

            return foundPath;
        }

        public boolean dfs(int n, int[][] graph, int start, int target, int nowPoint) {
            if (foundPath) {
                return foundPath;
            }
            if (nowPoint == target) {
                foundPath = true;
                return foundPath;
            }


            //每次去找途中开始的边
            Integer startEdge = startMap.get(nowPoint);
            if (startEdge == null || visited[startEdge]) {
                return foundPath;
            }

            //这里分叉到当前节点所有的边
            while (startEdge < graph.length && graph[startEdge][0] == nowPoint) {
                //下个节点
                int nextNode = graph[startEdge][1];
                //检查过这条边
                visited[startEdge] = true;
                //找下一个节点
                dfs(n, graph, start, target, nextNode);
                if (foundPath) {
                    return foundPath;
                }
                startEdge++;
            }


            return foundPath;


        }
    }
//leetcode submit region end(Prohibit modification and deletion)


}